
const matrix = [
  [...'-7--16-9-'],
  [...'-5-------'],
  [...'-9-73--6-'],
  [...'-32-----7'],
  [...'9--42-1-3'],
  [...'-----1--9'],
  [...'3--8--9--'],
  [...'8-5-97--1'],
  [...'7-----58-'],
]

function enumSpaces(matrix) {

  let sites = []

  for (let r = 0; r < 9; r++) {
      for (let c = 0; c < 9; c++) {
          if (matrix[r][c] == '-') {
              sites.push({ r, c })
          }
      }
  }

  return sites
}

const spaces = enumSpaces(matrix)

function digitsAroundSpace(space_index, matrix) {

  let [row, col] = [spaces[space_index].r, spaces[space_index].c]

  let digits = []

  for (let d of matrix[row]) {
      if (d != '-') digits.push(d)
  }

  for (let r of matrix) {
      let d = r[col]
      if (d != '-') digits.push(d)
  }

  let ninth_palace = [Math.floor(row / 3), Math.floor(col / 3)]

  for (let r = ninth_palace[0] * 3; r < ninth_palace[0] * 3 + 3; r++) {

      for (let c = ninth_palace[1] * 3; c < ninth_palace[1] * 3 + 3; c++) {

          let d = matrix[r][c]
          if (d != '-') digits.push(d)
      }
  }

  return digits
}

function availableDigits(index, matrix) {

  let exists = digitsAroundSpace(index, matrix)
  let available = []

  for (let d = 1; d <= 9; d++) {

      if (exists.indexOf('' + d) < 0) {
          available.push('' + d)
      }
  }

  return available
}

function search(space_index, matrix) {

  if (space_index == spaces.length) {
      return true
  }

  let digits = availableDigits(space_index, matrix)
  let [row, col] = [spaces[space_index].r, spaces[space_index].c]

  for (let d of digits) {

      matrix[row][col] = d

      if (search(space_index + 1, matrix)) {
          return true
      }
  }

  matrix[row][col] = '-'

  return false
}

search(0, matrix)
console.log(matrix)

